COMMENT ⊗   VALID 00014 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	.NSECP(Control Structure)
C00006 00003	.SSEC(Motivation)
C00009 00004	. SSSEC(The magnitude of AM's task)
C00018 00005	. SSSEC(Constraining AM's Search)
C00025 00006	.SSEC(The Agenda)
C00026 00007	. SSSEC(Why an Agenda?)
C00033 00008	. SSSEC(Details of the Agenda scheme)
C00040 00009	. SSSEC(Alternatives to the Agenda Scheme)
C00052 00010	.SSEC(AM as Heuristic Search)
C00053 00011	. SSSEC(Heuristic Search)
C00062 00012	. SSSEC(AM's Similarities to Heuristic Search)
C00066 00013	. SSSEC(AM's Differences from Heuristic Search)
C00071 00014	. SSSEC(Summary: Agendas and Heuristic Search)
C00073 ENDMK
C⊗;
.NSECP(Control Structure)

.BEGIN TURN ON "{}"

AM is one of  those awkward programs whose representations  only make
sense  if you  already understand how  they will  be operated on.   A
discussion of AM's control structure (this chapter and the next) must
thus precede  a discussion of  concepts and how they  are represented
(Chapter  {[2]  KNOWL}).   Sections  1.3 and  1.4 gave  the  reader a
sufficient knowledge of AM's "anatomy". For  his convenience, Section
{SECNUM}.1 will repeat the  relevant portions of that overview.  Thus
armed with  a cursory  knowledge of  the "statics"  of AM,  we  shall
proceed to describe in detail its "dynamics".


In theory, AM is a distorted kind of  heuristic search program.  This
is discussed in {SECNUM}.3.  In a more pragmatic sense, the top-level
flow of control is governed by job-list or agenda of plausible tasks.
Motivation for -- and details of  -- this scheme are found in Section
{SECNUM}.2.

Chapter {[2]  HEURS} deals with the way AM's heuristics operate; this
could be viewed as the "low-level" control structure of  AM.  Chapter
{[2]  KNOWL}  contains some  detailed  information  about the  actual
concepts (and heuristics)  AM starts  with, and a  little more  about
their  design  and  representation.   Chapter  {[2]  EXAM2}  presents
several examples which clarify AM in action.

.END

.SSEC(Motivation)

Before beginning,  it is crucial  that the reader  know a  little bit
about how  concepts are stored.

AM is a  collection of  data structures, called  ⊗4concepts⊗*.   Each
concept is meant  to intuitively coincide with  one mathematical idea
(e.g.,  Sets, Union,  Trichotomy).   As such,  a concept  has several
aspects or  parts, called  ⊗4facets⊗*  (e.g., Examples,  Definitions,
Domain/range,  Worth).   If  you wish  to  think of  a  concept as  a
"frame", then its facets are "slots" to be filled in.  Each facet  of
a concept will either be totally blank, or  else will contain a bunch
of  ⊗4entries⊗*. For  example, the  Algorithms  facet of  the concept
Union may point to several  equivalent LISP functions, each of  which
can be used  to form the union  of two sets$$ The  reasons for having
multiple algorithms  is that sometimes AM will want one that is fast,
sometimes it  will be  more  concerned with  economizing on  storage,
sometimes  AM  will want  to  "analyze" an  algorithm,  and for  that
purpose it must  be a  very un-optimized  function, etc.  $ Even  the
"heuristic rules" are merely entries on the appropriate kind of facet
(e.g., the entries on the Interest facet of the Structure concept are
rules for judging the interestingness of Structures$$ A typical such rule
is: A structure is interesting if one element is ↓_very_↓ interesting.
$.)

. SSSEC(The magnitude of AM's task)

At any moment, AM will consist of a couple hundred$$ AM starts with a
little  over a  hundred  concepts, and  grows to  about  300 concepts
before running out of time/space. $ concepts, each of which  has only
⊗4some⊗* of  its facets filled in.  Most facets of most  concepts are
totally  blank.  AM's basic activity is  to select some facet of some
concept, and then try to fill in some entries for that slot$$ This is
not quite  complete. In  addition to filling  in entries for  a given
facet/concept pair, AM may wishto  check it, split it up,  reorganize
it, etc. $. Thus the  primitive kind of "⊗4task⊗*" for AM  is to deal
with  a particular  facet/concept pair.   A  typical task  looks like
this:

.B0

⊗6Fill in the "Examples" facet of the "Primes" concept⊗*

.E

If the average concept has ten or twenty blank facets, and  there are
a  couple  hundred  concepts,  then   clearly  there  will  be  about
20x200=4000  tasks for AM to work on, at  any given moment.  It turns
out that executing a task will take around 10 cpu  seconds, so only a
small percentage of these tasks can ever be executed.

Since most  of the  "legal" tasks will  never be explored,  what will
make AM appear "smart" -- or a loser -- are its choices of which task
to pick  at each moment.   So it's  worth AM's spending  a nontrivial
amount  of time  deciding which  task to execute  next. On  the other
hand, it had better not be ⊗4too⊗* much time, since a task  does take
only 10 seconds.

One question that must be discussed is: What percentage of AM's legal
moves  (at  any  typical  moment)  would  be  considered  intelligent
choices, what percentage would be dubious, and  what percentage would
be  nonsequitors.   The  answer  comes  from  empirical results.  The
percentages  vary  wildly  depending  on  the  previous  few   tasks.
Sometimes, AM  will be  obviously "in  the middle"  of a sequence  of
tasks, and  only one or two of the  legal tasks would seem plausible.
Other times, AM has just  completed an investigation by running  into
dead-ends, and there may be hundreds of tasks it could choose and not
be criticized.   The median case would perhaps permit about 10 of the
legal tasks to be judged reasonable.

It is  important for AM  to locate  one of these  currently-plausible
tasks,  but  it's not  worth  spending much  time  deciding which  of
⊗4them⊗* to work on next.

So AM still faces  a huge search.  Its choice of  tasks is made  even
more important  due  to the  10-second "cycle  time" --  the time  to
investigate/execute  one task.   A  human user  is watching,  and ten
seconds is  a nontrivial  amount of  time to  him.  He can  therefore
observe, perceive, and  analyze each and every task  that AM selects.
Even  a few bizarre  choices will  greatly lower his  opinion of AM's
intelligence.

AM can't  afford to be  fast and  simple-minded. Unlike, e.g.,  chess
programs, every state  considered can be seen by  the user. Even more
important, the combinatorial explosion  in the domain of  mathematics
makes chess' explosion look like a firecracker.

Chess programs have had to face the  dilemma of the trade-off between
"intelligence"  (foresight,   inference,  processing,...)  and  total
number of board situations  examined.  In chess, the  characteristics
of  current-day machines  have  to date  unfortunately still  favored
fast,  nearly-blind$$  i.e., using  a  very simple  static evaluation
function.  That situation will probably change in the next few years.
$ search.  Although machine  speed may allow blind search to win over
symbolic inference for  shallow searches, it  can't provide any  more
than    a   constant    speed-up    factor   for    an    exponential
game/search/problem.

The  more  legal moves  there  are  at each  moment,  the  louder the
combinatorial explosion. For Nim, the number of legal moves is always
about 2.  For chess, this averages  out to around 50; for math theory
formation it's  in the thousands. The louder that explosion, the less
help machine-speed will be.

Since the  number of "legal  moves" for AM  at any  moment is in  the
thousands,  it  is unrealistic  to  consider "systematically"  (i.e.,
exhaustively) walking through the entire space that AM can reach.  In
AM's task, there is so much "freedom" that symbolic inference finally
⊗4can⊗*  win over the  "simple but fast"  exploration strategy$$ Paul
Cohen disagrees.  Time will tell:  this is the kind of question  that
can only be answered empirically. $.

The above comparison of AM to chess programs is valid only if the two
searches are of about the same depth, of course. Coincidentally, both
a chess master and a mathematician will produce searches of about the
same depth:  between 10  and 100. By  the time the  mathematician has
sunk that  deep into  new concepts  and theorems,  he's developed  an
entirely new theory.  By the time the  master has delved that deeply,
he's  fully formulated his plans  -- and exhausted the  limits of his
(albeit large$$ Reference: [Simon] $ mental chess vocabulary.

. SSSEC(Constraining AM's Search)

The last section should have convinced us that AM must expend a fair amount of energy
deciding which task to work on next each time. Now that the committment is made,
let's think about how to use that time: how can Artificial Intelligence
help AM make that choice in a plausible way?

A  great deal  of  heuristic  knowledge is  required  to  effectively
constrain the processing necessary to  zero in on a good task to work
on next.  This is done in two stages.

.BN

λλ A list of plausible facet/concept pairs is maintained. Nothing can
get onto this  list unless there is  some reason why filling  in that
facet of that concept would be worthwhile.

λλ  All the plausible tasks  on this "agenda list"  are ranked by the
number and strength of the  different reasons supporting them.   Thus
the facet-concept  pairs near the  top of the  list will all  be very
good tasks to work on.

.E

The first of these constraints is akin  to replacing a ⊗4legal⊗* move
generator by  a ⊗4plausible⊗*  move generator.   The  second kind  of
constraint is akin to using a heuristic evaluation function to select
the best move from among the plausible ones.

The ⊗4agenda⊗* is a  data structure which is  a natural way to  store
the  results of  these  procedures.  It is  (1)  a  list of  all  the
plausible tasks which have been generated, and (2) it is kept ordered
by the numeric  estimate of how  worthwhile each  task is. A  typical
entry on the agenda might look like this:

.WBOX(4,9) ; TABS 12,42  TURN ON "\"
MBOX      Fill in  the  EXAMPLES  facet of the  PRIMES  concept $
MBOX				⊗8~⊗* $
MBOX				⊗8~⊗* $
MBOX				⊗8~⊗*   ⊗4Reasons for filling in this facet⊗* $
MBOX				⊗8~⊗* $
MBOX				⊗8↓⊗* $
MBOX \⊗8⊂∞α→\⊃ $
MBOX \⊗8~⊗6 1. No examples of primes are known so far. \⊗8~⊗* $
MBOX \⊗8~⊗6 2. Focus of attention: AM just defined Primes. \⊗8~⊗* $
⊗8~\%∞α→\$∞ →~
MBOX				⊗8~⊗* $
MBOX				⊗8~⊗* $
MBOX				⊗8~⊗*   ⊗4Overall value of these reasons⊗* $
MBOX				⊗8~⊗* $
MBOX				↓ $
MBOX			       ⊗2250⊗* $
.EBOX

.COMMENT The funny line above is due to the fact that the MBOX separator is $ ;


The actual  top-level control structure  is simply  to pluck the  top
task   from  the  agenda  and   execute  it.  That   is,  select  the
facet/concept pair  having the best  supporting reasons,  and try  to
fill in that facet of that concept.

While a task is being executed, some new tasks might get proposed and
merged  into the agenda.  Also, some new concepts  might get created,
and this, too, would generate a flurry of new tasks.

After AM  stops filling  in entries for  the facet  specified in  the
chosen  task, it  removes that  task from  the agenda,  and  moves on
whichever task is the highest-rated at that time.

Near the  end  of  this  chapter,  AM  will  be  squeezed  into  (and
contrasted against) the  "heuristic search" paradigm. Each  task will
be viewed as a "node" in that search space.

The reader probably has  a dozen good$$ A question is "good" if (i) I
have anticipated it, and (ii) It has a snazzy answer. A typical "bad"
question will begin "Yes, but why  didn't you..." $ questions in mind
at  this point (e.g., How do the reasons  get rated, How do the tasks
get proposed, What happens after  a task is selected,...).   The next
few sections  should answer most  of these. The  more judgmental ones
(How dare you propose a numeric calculus of plausible reasoning?!  If
you slightly de-tune all those numbers, does the system's performance
fall apart?...) will be answered in Chapter 6.

Henceforth,   I'll  use  the  following   all  interchangably:  task,
facet/concept pair, node,  job. This should  break up the  monotony$$
and cover my sloppiness. Seriously,  thanks to English, each of these
terms  will  conjure  up  a  slightly  different  image:  a "job"  is
something to do, a "node" is  an item in a search space,
"facet/concept pair" reminds  you what
the format  of  a  task  is.  $.   Similarly,  the  ordered  list  of
facet/concet pairs will also be referred to  as the job-list of jobs,
and as the agenda of tasks.

.SSEC(The Agenda)

. SSSEC(Why an Agenda?)

This subsection  provides motivation for  the following one,  by arguing
that a  job-list scheme is a natural mechanism  to use to manage the
task-selection problem AM faces. Recall that AM must zero in on one of the
best tasks$$ 
It isn't meaningful to demand that AM find ↓_the_↓ "best" task, since the
criteria will ultimately depend on personal aesthetics and on hindsight. $
to perform next, and it repeatedly makes this choice.

One of  the distinguishing  characteristics of  AM's  search for a good task is
enormous size of its search space. At each moment, there might be thousands
of directions to explore (plausible tasks to consider).

<<The next para. is redundant. Eliminate it? >

In such a situation, it  is necessary to choose carefully  which path
to trod, which
facet/concept pair to investigate next.
A blind, systematic, exhaustive search scheme  (like  breath-first or
depth-first search)  would simply  not be suitable. Recall  that  we
shall judge AM not by what it finds, so much as by the quality of its
entire sequence of activities.

If all the legal tasks were written out, and reasons were thought up to
support each one, then perhaps we could order them by the strength of those
reasons, and thereby settle on the "best" task to work on next.
In fact, many of the tasks would have no reasons behind them, and many would
have very good reasons. AM would never get around to working on a task which
had no reasons, since new plausible tasks keep being proposed.
So there is no point explicitly remembering a pending task unless it
has some good reasons supporting it. Conversely, it is important to
store a list of all the plausible (reason-supported) tasks.

The natural solution is to maintaina list of those legal tasks which have
some good reasons tacked onto them, which justify
why each task should be  executed, why it is plausible.


.ONCE TURN ON "{}"

Also, we can suppose  the existence of a function which can provide a numeric
rating, a priority value, for any given task.
This magic function would look  at a
given  facet/concept pair, examine all  the associated  reasons
supporting  that task, and  would compute how worthwhile  it would be
for AM to spend some time now filling in that  facet of that concept.
AM  actually incorporates  a  formula for  this purpose;  it  will be
described later in this chapter, on page {[3] FORMULA}.

At least implicitly, then,  we have hundreds of plausible tasks, and a  numeric
rating for each task. The obvious control  algorithm is to choose the
task with the highest rating, and work on that one next.

So the natural control structure is that of an ordered list of tasks,
where the program repeatedly plucks the highest task and executes it.
While it's executing, some new tasks  might get proposed and added to
the list of tasks. Reasons are kept tacked onto each task on this list,
and form the basis for the numeric priority rating.

Give  or take a few features, this notion  of a "job-list" is the one
which AM uses. It is  also called an ⊗4agenda⊗*.$$ Borrowed  from Kaplan's
term for the job-list present in KRL. [Bobrow & Winograd] $ "A task
on the agenda" is the same as "a job on the job-list" is the same  as
"a facet/concept  pair which has  been proposed" is  the same  as "an
active node in the search space".

The next subsection  presents this scheme in a fair amount of detail.
There are in fact many details we haven't specified,
and you probably have many questions. If not, here are a couple: How
does AM  know when  to stop the chosen task, and move on  to a new one?
Do tasks get removed from the agenda even if they fail?

The  subsection  after  that will  discuss  some  alternatives  to an
agenda.  For example, why not let each task be  a "process" which can
wake/sleep, etc.?  Why not have the "nodes" of AM's search correspond
to the concepts, and "expanding  a node" would then involve  spending
some time to fill in all its facets, one after another?

. SSSEC(Details of the Agenda scheme)

.AGENDASEC: SECNUM

.AGENDASSEC: SSECNUM

.AGENDAPAGE:

At each moment, AM has many plausible tasks  (hundreds or even thousands) which
have  been  suggested for  some  good reason or  other,  but  haven't been
carried out yet.  Each task is  at the level of working on a  certain
facet of a certain concept: filling  it in, checking it, etc.  Recall
that  each task also  has tacked onto  it a list  of symbolic reasons
explaining why the task is worth doing.

.XGENLINES←XGENLINES-1

In addition,  a  number (between  0  and 1000)  is attached  to  each
reason,  representing some  absolute  measure of  the  value of  that
reason (at the moment).  One  global formula$$ Here is that  formula:
{TURN ON  "&↑↓" }
Worth(J) =  ||SQRT(SUM R↓i&↑2)||  x α[ 0.2xWorth(A)  +
0.3xWorth(F)  + 0.5xWorth(C)α],  where J =  job to  be judged =  (Act A,
Facet F,  Concept  C),  and {R↓i}  are  the ratings  of  the  reasons
supporting J.   For  the sample  job pictured  in the  box, A=Fillin,
F=Examples,  C=Sets, α{R↓iα}=α{100,100,200α}.  It will be repeated --
and explained -- in Section {α[2α] HEURS}.{α[2α] FORMULASSEC},  on
page {α[2α] FORMULA}. $  combines all the reasons' values  into a single priority
value for the task as a whole.

.COMMENT Beware of the braces in the last para.;

.XGENLINES←XGENLINES-1

A typical entry on the agenda might look like this:

.WBOX(6,10)
MBOX TASK: Fill-in examples of Sets $
MBOX PRIORITY: 300 $
MBOX REASONS:  $
MBOX		100: No known examples for Sets so far. $
MBOX		100: Failed to fillin examples of Set-union, for lack of examples of Sets $
MBOX 		200: Focus of attention: AM recently worked on the concept of Set-union $
.EBOX

To reiterate, a task's  priority really does depend on  the worths of
the reasons attached to the task.

Notice the similarity of this to the initial few lines which AM types
just after it selects a job to work on:

.BEGIN NOFILL PREFACE 0 TURN OFF "{}" TURN ON "↑↓\" TABS 18,21 SELECT 3

***Task 2.
Filling in examples of the following concept: "Sets".

	3 Reasons:\(1) No known examples for Sets so far.
\(2) Failed to fillin examples of Set-union, for lack of examples of Sets.
\(3) Focus of attention: AM recently worked on Set-union.

.E

The flow of control may appear  quite sophisticated (intelligent?) to
the user,  but the top-level mechanism is  trivial: AM picks the task
with the highest priority value,  and tries to execute it. Since  the
form of the global "uniting" formula is also unimportant, we conclude
that  the  "intelligence"  has  been  pushed  down  into the  careful
assigning of reasons (and their values) for each proposed task.

Meanwhile, back at  the top-level,  AM has begun  to execute the  top
task. As a side effect, new jobs occasionally get added to the agenda
while the task is being executed.   The global priority value of  the
task also indicates how  much time and space this  task deserves. The
sample task above might rate 20 cpu seconds, and 200 list cells. When
either of these resource quanta is used up, AM terminates work on the
task, and  proceeds to pick  a new  one.  In  the case of  filling in
examples of sets, the space allowed will be used up quickly.

There are two big questions now:

.BN

λλ Exactly how is a task proposed and ranked?

.INDENT 8,0,0

How is a plausible new task first formulated?

How do the supporting reasons for the task get assigned?

How does each reason get assigned an absolute numeric rating?

Does a task's priority value change? When and how?


.ONCE INDENT 4,0,0

λλ How does AM execute a task, once it's chosen?

Exactly what can be done during a task's execution?

.END

.SS1←SSECNUM + 1;

.SS2←SSECNUM + 2;

.S2←SECNUM + 2;

.COMMENT BOXTOP(5);

.ONCE TURN ON "{}α"

Section  {SECNUM}.{SS1} will  deal with  executing a given  task, and
section {SECNUM}.{SS2} will  return to the questions  surrounding the
proposing --  and ranking --  of tasks. Chapter  {S2} will illustrate
most of  these  ideas.  A detailed  discussion  of  difficulties  and
limitations   of    these   ideas   can    be   found    in   Section
{α[2α]DIFSECNUM}.{α[1α]DIFSSECNUM}, on page {α[3α]DIFSEC}.

.COMMENT BOXBOT(0,89);

. SSSEC(Alternatives to the Agenda Scheme)

<<This section is bizarre/out of place/too long >

Below  are  some  reasonable  questions  --   and  answers  --  about
alternative ways of managing a large heuristic search like AM.

.BN


λλ Why  not let a "node"  be a concept, instead of  the artifice of a
facet/concept/reasons structure?

.INDENT 8

In a standard heuristic search, a particular operation is  applied to
a particular  node, and new nodes  result.  For exmaple,  in chess, a
"node"  might be a  board configuration, and an  "operation" might be
castling.   In such searches,  the action  "create a  new node X"  is
trivial.  It may eat  up some memory space (e.g., storing a new board
position), but growing a new  node rarely requires much "work",  much
processing time.

In  scientific  concept  formation,  viewed  as  a  heuristic  search
process,  the situation is  quite different,  however. A "node"  is a
highly-strucured concept. We may wish to create it after we  find out
just a couple of its facets  (e.g., its definition and one inteesting
conjecture  involving   it).    At  that  moment,  we  would  have  a
partially-filled-out new node. A  few facets would have  some entries
in them, but most facets  would be blank.  By the usual definition of
"creating a node", we would have to face, a this stage, about  twenty
tasks, many of  them time-consuming (e.g.,  fill in some  examples of
this  concept, fill  in some  generalizations of  it,...).   For each
blank facet, some time would have to be spent filling it in.

But most of  these activities are not  cost-effective. Too much  time
would be  spent, for too  little reason.   Clearly, we don't  want to
generalize and  specialize ⊗4every⊗* new concept$$ This would in fact
cause an  infinite regress:  When concept X  is to  created, we  must
first find new concepts which are generalizations of X; but to create
such  new   concepts,  we   must   first  find   generalizations   of
↓_them_↓,...$.   As soon as  examples of a  concept X are  filled in,
some pattern may  be perceived.  At that moment, it is clearly better
to go off  and explore that  pattern, than  to blithely continue  on,
filling in all  the other facets of  X.  As an  extreme case, suppose
⊗4no⊗*  examples of  X were found.  Then X  might be  vacuous, and it
would be absurd to spend time trying to specialize it.   On the other
hand, there would then be good reason to try to ⊗4generalize⊗* X.  In
fact, perhaps one of the best ways  for AM to spend its time at  that
moment  would be  to  progressively generalize  X  until one  of  its
generalizations ⊗4did⊗* have some examples.

In other words,  it seems reasonable that sometimes we'd like to quit
working on "fleshing out" the blank facets of a concept, in  order to
explore  some particular  new concept,  or in  order to  perform some
specific  task.  In each  case, some good  reasons will have appeared
which  induce  us to  break  away  from  the  plodding  "filling-out"
activities  we were just  engaged in.   Specific reasons  always have
priority over general inertia (focus of attention).

.INDENT 4

λλ  We  could  let  the   reasons  act  like  little  programs,   and
⊗4↓_interrupt_↓⊗* each  other.   When  a reason  for  doing X  gained
control, the  task X would be started.  But  then how do we cope with
several reasons pro and  con a given activity?   Also, when one  task
has been done, how can we be sure where the best place to "return" to
is?


λλ  We could consider that  we have one central  program, but that it
can ⊗4↓_recurse_↓⊗* whenever a  better task becomes evident.  One can
then  imagine  that  the   control-stack  would  contain  a  list  of
interrupted tasks,  getting  more  and more  worthwhile  (better  and
better reasons) as we proceed toward the current moment.  The current
task can't be  interrupted, except for the sake of performing an even
⊗4more⊗* interesting task.  If the current task finishes,  the normal
recursion process  will take us  back to finish  the last task.   But
recent  discoveries may dramatically effect the worthwhileness of the
activities on the control stack;  how could we reorder them?   Within
the standard function-calling scheme, this can't be done.


λλ It  sounds like  we might need  to have a  ⊗4↓_process_↓⊗* scheme,
involving many active tasks, which can go to sleep and wake up  under
certain conditions.  Recall that most of  the reasons will not really
be  in support  of a task  the size  of "fill  out a concept  X", but
rather one of the size  "fill out facet F  of concept X".  But  these
tasks  only use  up  a  few seconds  each  (say  averaging around  15
seconds).   Is it really worth it  to worry about interrupting one of
these tasks, once it's started?   Is it worth using a  hundred memory
cells to store the state of process that would only use up 5 more cpu
seconds if we let it wake up and  continue?  What if we have to  keep
around a thousand partially-complete tasks?  Probably not worth it.


λλ Most of the tasks we have hanging around are fairly independent of
each   other,  so   perhaps  we   could  exploit   the  power   of  a
⊗4↓_multi-processor_↓⊗*.  But we have thousands of little  tasks, and
they spawn  new ones.  Well, if we  only could run  the program  on a
10,000-processo machine (like the proposed Hypercube machine of <<get
this reference>)...  Well, when  one of these  is built  -- and  good
systems  software exists  for it  -- this  may be  worth considering.
Even so, the reults of experiment 2  (see Sec.  5.3) indicate that  a
very important  mechanism is the  one whereby highly-rated  new tasks
get suggested dynamicly, while the current task is executing.  So the
gain in  speed would  only  be a  small factor  (maybe one  order  of
magnitude --  not three).  A  much more standard criticism  of such a
scheme  is that it only chops the time  by a contant amount (at best,
10,000), wheras the tasks grow exponentially.


λλ The most  obvious scheme is to  just ⊗4↓_execute them all_↓⊗*,  in
some  order.   Even  though  we may  as  well look  on  each task  as
indivisible, we simply can't afford to spend 15 cpu seconds executing
each one:$$ Please forgive the pragmatic discussion  that is about to
occur, but the reader probably will sympathize with the need to worry
about cpu time and space.  $ that would use up 100,000  seconds (days
of cpu time). For each new  concept created, about 20 new tasks would
be proposed.   The process of "adding a node" would thus use up 5 cpu
minutes of time.

λλ Well, what do computers do when they have lots of  tasks to do, of
varying  priority?  Often,  they make  out an  agenda, a  schedule of
things to do. The most important  tasks are tackled first, and so  on
down the line. Typically there will be a ⊗4↓_dynamic scheduler_↓⊗* to
pick the  next task at each  moment.  Maybe our  system should do the
same thing, namely schedule all the tasks, to choose them in order of
decreasing estimated  worth.   That is,  pick the  one with  the best
reasons  supporting it, and  execute it.   Repeat this Select-Execute
procedure  over and  over  again.    If a  new,  valuable  task  gets
suggested, it can be merged into the agenda.  If the new task is even
more valuable than the current  one, so what?!   This will be a  rare
occurrence, and anyway the current task will  probably be nearly done
(so we give up an extra few seconds here and there).

.END

.SSEC(AM as Heuristic Search)

.ONCE TURN ON "{}"

As the title of this section -- and this thesis -- proclaims, AM is a
kind  of  "heuristic search"  program.   That  must mean  that  AM is
exploring  a  particular  "space,"  using  some  informal  evaluation
criteria   to   guide   it.     Sections   {SECNUM}.{SSECNUM}.2   and
{SECNUM}.{SSECNUM}.3 will present this view in detail.  First, let me
define what a heuristic search is. Readers familiar with this concept
may skip the first subsection entirely.

. SSSEC(Heuristic Search)

Heuristic gourmets  sometimes find  it useful  to classify  heuristic
searches  based on  their taste,  but for  our modest  purposes we'll
stick to just one flavor$$ Rocky road. $.

The activity we  wish to model  using the search  must be phrased  in
terms  of  states  and  operators.  The   operators  are  capable  of
transforming  some  states into  different ones.  Given  some initial
configuration of states, the  "game" is to repeatedly apply  opertors
to states.  The objective will either  be a particular state,  or any
state satisfying  some well-defined criteria.  Finally, some rules of
thumb must  be  present, to  guide  the player  as he  chooses  which
operator to apply to which state next.

This is  a rather confused presentation;  a superior one  is found in
Chapters...  of  [Nilsson]. Perhaps a  more graphical  interpretation
will be  helpful.   A  graph is  a  bunch of  little circles,  called
⊗4nodes⊗*, which represent  the states of the search, plus a bunch of
arrows,  called  ⊗4arcs⊗*,  which   represent  applications  of   the
operators. 
Each node has a name, which is written inside its little circle, and
each arc may have a label, which is written alongside it.
If an arc points from node  X to Y and is labelled F, then
we  assume  that opeator  F  was applied  to  state X,  and  that the
resultant  state  was  Y.    

.B0

	    ⊂∂∂∂∂∂∂∂⊃	
	    ~	    ~
	    ~	X   ~
	    ~	~   ~
	    ~	~   ~
	    ~	~ F ~
	    ~	~   ~
	    ~	↓   ~
	    ~ 	Y   ~
	    ~	    ~
	    %∂∂∂∂∂∂∂$

.E


The  whole  idea  of  "search"  in  this
interpretation is to carefully enlarge the graph (to keep drawing new
arcs and nodes).


Each node can have several arcs pointing to it; each arc can point to
several different nodes; and each arc can point ⊗4from⊗* a collection
of  different nodes.   Thus an  arc is like  an arrow which  can have
multiple heads and tails:

< Diagram of a graph >

.B0

A			Z	   W
~\		       /	  /
~ \	B←∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂C	 /			Q
~  \    ↓		 ↑	/		       /
~   R∂∂→D∂∂∂∂∂∂→E∂∂∂∂∂∂∂→H←∂∂∂∂∂∂∂∂∂∂∂L∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂
~  /						       \
~ /							\
↓/							 G
U								

.E

Some more terminology may come in handy here.  If an arc  points from
X to  Y, we  say that  Y is  a ⊗4successor⊗* of  X, and  that X  is a
⊗4parent⊗*  of Y. If a chain of arrows leads  from X to Y... to Z, we
say that Z is a ⊗4descendant⊗* of X, and that X is an ⊗4ancestor⊗* of
Z.  If there is one function which can generate all successors of any
given node, we call  that the ⊗4successor  function⊗* of the  search.
Any function  which is  used to  informally rate  the "value" of  any
given node is called a ⊗4heuristic evaluation function⊗*.

Let's give a few examples.

<<Rewrite this chess example. >

In a chess-playing program, a natural choice is to make each possible
board position correspond  to a state. The  operators are simply  the
legal  moves of  the  game.  So there  would  be  an operator  called
"Move-rook",  which  could  transform  a  given  state  into a  large
collection of new ones, which differed from the original  one only in
that  one rook  had been  (legally) moved  along some  rank  or file.
Sometimes, this operator would yield ⊗4no⊗* successors (e.g., if  one
rook  is gone  and  the  other is  pinned  against  the king).    The
heuristic evaluationfunction would  be a function which looked at any
board situation, and counted material, examined control of  key areas
of the  board, and in other  ways somehow pieced together  an opinion
about just  how good this board really is (from the standpoint of one
particular  player).   Each  player  might have  his  own  evaluation
function, or  they might both  use the same  one, or they  might vary
which evaluation function they use  depending on recent moves,  their
opponent's   reputation,  random   chance,  etc.      As  with   many
non-chess-playing  humans,  there is  no  sense of  a  definite goal,
except just  prior to  mating.  Rather, the  typical approach  is  to
generate some of the successors to the current board situation (using
heuristic  guidance  to  only  generate  plausible  moves),  and then
evaluate each successor state using the evaluation function. The best
of  these states would  then be  expanded in turn  (i.e., all  of the
opponent's relies would be considered).  If the opponent had  ⊗4any⊗*
good reply to one of the moves, that move  would then have its rating
lowered  accordingly. This process --  which is called ⊗4minimaxing⊗*
-- would be continued as long as time permitted. When forced to halt,
the successor of the current state  which had the highest value would
be  chosen as the  actual successor (i.e., the  corresponding move to
alter the  board to  that state  would then  be made),  and it  would
become you oppenent's turn.


<< Give a couple more examples of heuristic search. >

In theorem-provers,  each operator is a rule  of inference.  Applying
an operator adds one more wff  to the list of known true  statements.
So in some  sense ⊗4all⊗* paths lead to  a "goal", the problem  is to
find a  short, direct path. A solution is "good"  if it consists of a
very short path leading to an  acceptable goal node.  The quality  of
the path is very important.


. SSSEC(AM's Similarities to Heuristic Search)

AM explores mathematics by selectively enlarging  itself: AM ⊗4is⊗* a
body of mathematical knowledge (concepts, plus the wisdom to use them
effectively).  AM is a heuristic search program, much like  the chess
and theorem-proving  programs just  desribed.  To  see this,  we must
explain  what the nodes of AM's search  space are, what the operators
or links are,  where the heuristic  information comes into play,  and
what the evaluation function is.

AM's space can be consisered to consist of a bunch of nodes which are
each a facet/concept pair (a primitive task on AM's agenda of  things
to do).   In  one sense, the  successor function  is "EVAL" --  i.e.,
given a task,  execute it.  In a more meaningful sense, the operators
are the heuristic rules that AM uses to suggest new tasks  and create
new concepts.   While a task is executed (a  node is being expanded),
several new  tasks may get suggested (other nodes will be pointed to:
the successor nodes of the current one).  Each arc  in the space will
thus be a reason for executing the node it points to.  When a task is
suggested (by some heuristic),  it is tagged with  a list of  reasons
explaining why it  might be worthwhile. The evaluation  function need
only  scan all the nodes  (all the facet/concept  pairs), and examine
each's list of reasons.   In fact, experiments show that the  precise
form of  the evaluation function  is unimportant$$ See  experiment 3,
page...,  Section... $.  AM has a  definite algorithm for rating ithe
nodes of its space, and yet certainly has no  specific goal criteria:
it can't quit just because a dynamite task has been proposed. AM goes
on forever$$ Technically, forever is about 100,000 list cells $.


This is probably unclear, so perhaps a picture will help:

<<Draw a graph: AM as heur search. >

Notice that... <<Things to notice about that graph. >



. SSSEC(AM's Differences from Heuristic Search)

There are several difficulties  and anomalies in forcing AM  into the
heuristic search paradigm.  For example, the main entities that AM is
concerned with are concepts,  and yet the  nodes of its search  space
are  merely  pointers to  particular  empty  facets.   In  a  typical
heuristic search, the nodes are intimately ties up with the intuitive
"states" of the situation.

Another anomaly is  that the operators which  AM uses to enlarge  and
explore  the space of  concepts are themselves  mathematical concepts
(e.g., some heuristic rules result in the creation of new ones). Thus
AM should be viewed as a mass  of knowledge which enlarges ⊗4itself⊗*
repeatedly.    As  far  as I  know,  all  previous  systems kept  the
information they "discovered" quite  separate fromthe knowledge  they
use to make discoveries$$ Of course this is typically because the two
kinds of knowledge are very different: For a chess-player, first kind
is "good board positions," and the second is "strategies for making a
good move." $.

Let me  reemphasize at this time  that AM has  no well-defined target
concepts or target relationships.  Rather, its "goal criteria" -- its
sole  aim  --  is  to  preserve  the  interestingness  level  of  the
activities  it performs, of  the top tasks  on the agenda.   We don't
care what AM does --  or misses -- so long  as it spends its time  on
plausible tasks.   There is no  fixed set of theorems  that AM should
discover (AM is thus not like a typical ⊗4problem-solver⊗*), no fixed
set  of traps  AM  should  avoid  (AM is  thus  very  different  from
⊗4game-players⊗* like chess programs).

For example,  there is no stigma  attached to the fact  that AM never
discovered real  numbers$$  There are  many  "nice" things  which  AM
didn't -- and can't -- do: e.g., devising ↓_geometric_↓ concepts from
its initial simple set-theoretic knowledge.  Paul Cohen has indicated
that this would be a supremly exciting development: the  invention of
geometry -- and  all the tools it  provides -- by a  system which has
neither  geometric  intuition  built  into  it,  nor  definitions  of
geometric concepts.  I do not think this possible; see the section on
the  limitations of AM,  page...$; it  was rather surprising  that AM
managed to  discover ⊗4natural⊗*  numbers!   Even if  it hadn't  done
that, it would have been just as  acceptable$$ Acceptable to whom? Is
there really a  domain-invariant criterion for judging the quality of
AM's actions? See the  discussion in Section...,  on Page... $ if  AM
had simply gone off and developed ideas in set theory.

. SSSEC(Summary: Agendas and Heuristic Search)

<< Why the agenda mechanism is well-suited  to heur search algorithms
>

Consider  Nilsson's  description  of  depth-first  searching, and  of
breadth-first searching. He has us  maintain a list of "open"  nodes.
Repeatedly, we pluck the top one  and expand it. In the process, some
new  nodes may be added to the Open  list. In the case of depth-first
searching, they are added at the top; for  breadth-first search, they
must be  added at the  bottom. For heuristic  search, or "best-first"
search, they are  evaluated in  some numeric way,  and then  "merged"
into the already-sorted list of Open nodes.

This process is  clearly analogous to  the agenda mechanism  AM uses.
It  is also the  same as  the one used  in KRL [reference],  and used
earlier in Dendral$$ The "Predictor" part of DENDRAL. See [MI4 ref.].
$  The main  difference  is that  in AM,  symbolic  reasons are  used
(albeit in trivial token-like ways) to decide whether -- and how much
-- to boost the priority of a task when it is suggested again.

Agendas are the canonical  kind of data structure for  a "best-first"
process.